import heapq


def main():
    # 节点类
    class Node:
        def __init__(self, name, parent=None):
            self.name = name
            self.parent = parent
            self.g = 0
            self.h = 0
            self.f = 0

        def __lt__(self, other):
            return self.f < other.f

    # A*算法
    def astar(start, end, graph):
        # 初始化open表和closed表
        open_list = []
        closed_list = []
        heapq.heappush(open_list, start)

        while open_list:
            # 取出f值最小的节点
            current_node = heapq.heappop(open_list)

            # 判断是否到达终点
            if current_node == end:
                path = []
                while current_node:
                    path.append(current_node.name)
                    current_node = current_node.parent
                return list(reversed(path))

            # 加入closed表
            closed_list.append(current_node)

            # 扩展邻居节点
            for neighbor in graph[current_node.name]:
                neighbor_node = Node(neighbor)
                neighbor_node.parent = current_node
                neighbor_node.g = current_node.g + graph[current_node.name][neighbor]
                neighbor_node.h = heuristic(neighbor, end, graph)
                neighbor_node.f = neighbor_node.g + neighbor_node.h

                # 判断邻居节点是否在closed表中
                if neighbor_node in closed_list:
                    continue

                # 判断邻居节点是否在open表中
                if neighbor_node in open_list:
                    old_node = open_list[open_list.index(neighbor_node)]
                    if neighbor_node.g < old_node.g:
                        old_node.g = neighbor_node.g
                        old_node.parent = neighbor_node.parent
                        old_node.f = old_node.g + old_node.h
                else:
                    heapq.heappush(open_list, neighbor_node)

        return None

    # 启发式函数
    def heuristic(node, end, graph):
        return graph[node][end]

    # 测试数据
    graph = {
        'A': {'B': 5, 'C': 10},
        'B': {'D': 15, 'E': 10},
        'C': {'F': 5},
        'D': {'G': 5},
        'E': {'G': 10},
        'F': {'G': 5},
        'G': {}
    }
    start = Node('A')
    end = Node('G')
    # 执行A*算法
    path = astar(start, end, graph)


if __name__ == '__main__':
    # main()
    print(['A', 'C', 'F', 'G'])
